/**
 * # Intersection between two lines / 两直线交点
 * 
 * https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line
 * 
 * NB:
 * 在维基百科条目中提及的以下行列式
 * |x1-x3 x3-x4|
 * |           |
 * |y1-y3 y3-y4|
 * 
 * 可以记作向量叉积的形式
 * cross((x1-x3, y1-y3), (x3-x4, y3-y4))
 * 或
 * cross(P1-P3, P3-P4) (其中P_i === (x_i, y_i))
 */
function segSegSect([h1, t1], [h2, t2]){

  let h1h2 = h1.diff(h2),
      h1t1 = h1.diff(t1),
      h2t2 = h2.diff(t2);

  let // 三个基本的行列式
      detA = h1h2.cross(h2t2),
      detB = h1t1.cross(h1h2),
      detS = h1t1.cross(h2t2),

      // 通过基本行列式得到的交点位置参数
      ratioA =  detA/detS,
      ratioB = -detB/detS,

      // 交点及用于判别方向的行列式
      point = h1.lerp(t1, ratioA),
      det = detS;

  let overHeadA = Math.abs(ratioA) < EPS,
      overTailA = Math.abs(1 - ratioA) < EPS,
      overHeadB = Math.abs(ratioB) < EPS,
      overTailB = Math.abs(1 - ratioB) < EPS;

  return {
      ratioA, // mag(point - head1) / mag(tail1 - head1)
      ratioB, // mag(point - head2) / mag(tail2 - head2)
      insideA: ratioA > EPS && ratioA < 1 - EPS,
      insideB: ratioB > EPS && ratioB < 1 - EPS,
      overHeadA,
      overTailA,
      overHeadB,
      overTailB,
      point, // point
      det  // h1t1 x h2t2 (for determining the direction)
  }
}

function sortSect([{ratioB: R1, det:D1}], [{ratioB: R2, det:D2}]) {
  return Math.abs(R1 - R2) < EPS
    ? D2 - D1
    : R1 - R2
}

/**
 * 
 * # Polygon get instersected by segment / 多边形被线段分割
 * 
 * 这里涉及到几个计算几何的性质
 * 
 * 0. Terminology:
 * 
 *    分割 / Cutting:
 *    以下描述中的「分割」均是指线段起始于多边形外部，并与多边形产生至
 *    少一个交点。如果线段起始于多边形内，则不认为它分割了此多边形。
 * 
 *    穿入 / Cut-into:
 *    分割线段与多边形产生一个交点的情形。
 * 
 *    穿过 / Cut-through:
 *    分割线段与多边形产生两个交点。
 * 
 *    结算分割 / Settlement of Cutting。
 *    实行分割动作。结算分割之后，分割线段不再存在，依据分割线段创建了新
 *    的多边形边。
 * 
 * 1. 如果一个线段分割一个凸多边形，可能的结果只有穿入和穿过，进入一定
 *    只有一个交点，而穿过会有两个交点。如果一个线段分割一个凹多边形，
 *    产生的交点如果是偶数个，那么结果一定是穿过，也就是说线段两端不在
 *    多边形内。因此对于所有的线段分割多边形的问题，都可以用交点的奇偶性
 *    来判断。
 * 
 * 2. 如果一个线段同时分割若干个不重合的多边形，那么线段只可能在其最后一
 *    个相交的多边形中为进入而不穿过的状态。这也就意味着这个线段只可能与
 *    最后一个相交的多边形产生奇数个交点，同时也意味着如果一个线段与这些
 *    多边形的全部交点为奇数个，那么肯定意味着此线段没有穿过最后一个相交
 *    的多边形。
 * 
 *    证明：如果线段在之前的多边形中即为进入状态，则不可能与最后一个多边
 *    形产生交点。
 * 
 * 3. 如果一个无自相交的连续线段分割一个多边形，其中每一个线段的结果依赖
 *    于上一个线段。它的状态可能是穿入，多边形内、穿过、多边形外。其中:
 *    a. 多边形外意味着此线段的两端都在形外且不分割多边形
 *    b. 穿入和穿过符合2.的描述
 *    c. 多边形内意味着此线段本身没有分割多边形，但是它的前驱可能是一个
 *       穿入或形内的线段，同时它的祖先有且仅有一个穿入的线段。
 * 
 * 4. 线段分割多边形的过程，即修改多边形并产生一个切口，切口顶点即线段终点，
 *    那么在切割进行的过程中，一个多边形内的线段和穿入的线段是等价的。只是
 *    由穿入线段产生的入口是交点，而多边形内是上一个穿入或多边形内的终点。
 * 
 * 5. 由4.得到，在分割多边形的进程中，并不存在自相交的连续线段，因为自相交
 *    总是后一个与前一个相交，但是在进行到后一个分割线段时，前一个已经完成
 *    了分割，并不再存在。因此后一个分割线段其实总是穿过由其之前的分割线段
 *    分割多边形候创建的新边。 
 * 
 * 6. 基于0. 如果连续线段事实上是起始于多边形内部，但我们需要创造出由外部
 *    分割多边形的效果，那么必须得使用连续线段两端线段的延长线（射线），这
 *    意味着在连续线段开始的线段是从所有多边形外进入，而最后的线段一定是穿
 *    出的。
 * 
 * 7. 基于以上关于分割的定义，我们认为所有的多边形都从同一个边形分割而来，
 *    因此多边形的关系只能是相离或相邻（共享至少一条边），而不存在overlapping
 *    的情形，那么此处当一个线段分割相邻的多边形时，就会出现一个问题，就是
 *    虽然在数据上共享的边分属于两个多边形，但在几何上它们是重合的线段，所
 *    以在几何上分割线段和这两个边产生的交点是同一个，或者至少位置相等。
 * 
 *    对于这种情况，我们只能通过边的方向来判断。首先所有多边形的点都按逆时针
 *    排序。其次经过分割的两条相邻的边分属于不同的多边形，共享部分的方向一定
 *    相反。因此我们可以判断，如果一个分割线段在其方向上遇到两个重合线段的交
 *    点，那么逆时针方向的边意味着是当前多边形要穿出的边，而顺时针则是另一个
 *    多边形待穿入的边。而总是需要先穿出再穿入，因此在重合的边上，我们也依此
 *    确定顺序。
 * 
 * 8. 最后，单个多边形中不允许存在重合的边。
 * 
 * @param {Vec[]} poly 
 * @param {{head, tail}} param1 
 */
function polysSegSect(polys, [hseg, tseg]) {

  return polys.map(poly => {
    const res = [];
    for (let i = 0; i < poly.length - 1; i++) {
      const sect = segSegSect([poly[i], poly[i+1]], [hseg, tseg]);
      res.push([sect, i, poly]);
    }
    return res.filter(([{insideA}]) => insideA);
  })
  .flat()
  .sort(sortSect)
  .pieceWise({
    head: ([{ratioB}]) => ratioB < EPS,
    body: ([{ratioB}]) => ratioB > EPS && ratioB < 1 - EPS,
    tail: ([{ratioB}]) => ratioB > 1 + EPS
  })
}

function extend(polys, sect, pos, ratio=1.5) {

  const get = {
    head: 'head',
    tail: 'last'
  }[pos];

  const add = {
    head: 'unshift',
    tail: 'push',
  }[pos];

  const segs = sect.diff();

  const side = polysSegSect(polys, segs[get]())[pos];
  side.sort(sortSect);

  if (side.length > 0) {

    const sectEnd   = sect[get]();
    const [{point}] = side[get]();

    sect[add](sectEnd.plus(point.diff(sectEnd).mult(ratio)));
  }
}

function sectBound(poly, sect) {
  return sect.diff((h, t, pos) => {
    let {head, tail} = polysSegSect([poly], [h, t])
    head = head[0]?.[0];
    tail = tail[0]?.[0];

    return (pos === 'HEAD')
    ? [head?.ratioB < 0 && !h.unextended ? head?.point : h, t]
    : (pos === 'TAIL')
    ? [h, tail?.ratioB > 1 &&  !t.unextended ? tail?.point : t]
    : [h, t]

  })
  .map(([h, t], i, a) => {
    return i === a.length - 1 ? [h, t] : [h]
  })
  .flat();

}

function polySect(polysOrig, sectOrig, {applyEnds, affected}={}) {

  let polys = [], 
      polysRest = [];

  if (affected && Array.isArray(affected)) {

    affected = [...new Set(affected)];
    
    for (let i = 0; i < polysOrig.length; i++) {
      if (affected.includes(i)) {
        polys.push(polysOrig[i].slice());
      } else {
        polysRest.push(polysOrig[i]);
      }
    }
  } else {
    polys = polysOrig.map(p => p.slice());
  }
  
  const sect = sectOrig;

  for (let i = sect.length - 1; i > 0; i--) {
    if (sect[i - 1] === sect[i]) {
      sect.splice(i, 1);
    }
  }

  if(applyEnds) {
    extend(polys, sect, 'tail');    
    extend(polys, sect, 'head');    
  }

  for (let i = 0; i < sect.length; i++) {
    sect[i].orig = true;
  }

  // 用来记录穿入的多边形，和当前的切口。
  let poly, cusp;
  for (let i = 0; i < sect.length; i++) {


    if (i < sect.length - 1 && sect[i].orig) {

      const {head, body, tail} = polysSegSect(polys, [sect[i], sect[i+1]]);

      for (let point of head) {
        point.sect = {type: 'end'};
      }

      for (let point of tail) {
        point.sect = {type: 'end'};
      }

      for (let point of body) {
        point.sect = {type: 'sect'};
      }
  
      // 对于第一个切割点，如果切割点在poly的边上，那么也要把它加入到
      // sect中。否则在后续的切割过程中它不会起作用。切割点在poly边上
      // 的情形不符合我们关于切割的定义，但是这可能是在切割之前，这个切
      // 割点是通过polysSegSect计算出来的。

      if (body.length > 0) {
  
        // 这里需要注意，由于在polygon中可能存在不同位置两个相同的点，
        // 我们必须按下标而不是那个点的对象，向polygon中插入新的点。
        // 在插入时为了不让插入的影响未被插入的下标，因此先将sections
        // 按照下标倒序排列。

        const sectionCopy = body.slice();
        sectionCopy.sort(([,A], [,B]) => B - A);

        for (let s = 0; s < sectionCopy.length; s++) {
          const [{point}, index, poli] = sectionCopy[s];
          poli.splice(index + 1, 0, point);
        }
  
        sect.splice(i + 1, 0, ...body.map(([{point}]) => point));
        i--;
        continue;
      }
    }

    let found = false;
    for (let p = 0; p < polys.length; p++) if(polys[p].includes(sect[i])) {
      found = true;
      if (cusp) {
        const head = polys[p].indexOf(cusp);
        const tail = polys[p].indexOf(sect[i]);
        
        tail.sect = {type: 'end'};

        const [orig, novo] = polys[p].mitosis(head, tail);
        polys.splice(p, 1, orig, novo);

        cusp = undefined;
        poly = undefined;

      } else {

        sect[i].sect = {type: 'sect'};
        cusp = sect[i];
        poly = polys[p];

      }

      if (found) break;
    }

    if (!found) {
      if (poly && cusp) {
        poly.splice(poly.indexOf(cusp) + 1, 0, sect[i], cusp);
        sect[i].sect = {type: 'sect'};
        cusp = sect[i];
      }
    }
  }

  return [...polys, ...polysRest];
}

function isPointInsidePoly(vec, poly) {
  if (!poly.isClosure()) {
    poly.toClosure();
  }
  return poly
    .diff((head, tail) => tail.diff(vec).cros(tail.diff(head)))
    .equal(Math.sign);
}